P1850 [NOIP2016] 换教室
Meaning
给定一张有 个点的无向图且有 次事件。我们可以选择其中 次事件作为特殊事件,有 的概率从当前点去点 $ b_i $,否则去点 $ a_i $。求期望距离。
Nothing with me, but Forever.
给定一张有 n 个点的无向图且有 n 次事件。我们可以选择其中 m 次事件作为特殊事件,有 pi 的概率从当前点去点 $ b_i $,否则去点 $ a_i $。求期望距离。
给定 n,k,和一个长度为 n 的 01 序列 {s}。我们需要把一个长度为 n 空白区间染色,你有如下两种操作:
求把空白区间全部染色的最小代价。
给定一棵 n 个结点的树,每个点的颜色是黑白中的一种。对于每个结点 u,选出一棵包含点 u 的连通子树,求其中白点数减去黑点数的最大值。
考虑在一个二维平面上,x 轴表示在一条直线上大楼排列的坐标,y 轴表示大楼的高度,那么第 i 栋大楼可以用 (i,hi) 表示。如果第 i 栋大楼与第 j 栋大楼满足 i<j 且 ihi≥jhj,那么第 j 栋大楼被第 i 栋大楼挡住而不可视见。求从 (0,0) 最多能看到的大楼数量。
悬线法裸题。
从 1 到 n 每个位置有一个高度为 hi,宽度为 1 的矩形。
求所有矩形覆盖面积中最大子矩形。